package nf.graph;

import java.util.AbstractCollection;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
import java.io.Serializable;

/**
 * Represents a directed graph.
 */
public class Graph extends AbstractCollection<Node>
	implements Serializable, PropertyBag
{
	/**
	 * The adjacency map of nodes.
	 */
	protected HashMap<Node, Set<Node>> nodes;
	private Map<String, Node> namedNodes;
	private Map<String, Object> properties;
	private Group rootGroup;
	private Set<GraphEventListener> listeners;
	private long edgeCount;
	
	static final long serialVersionUID = 3341910843948609807L;
	
	/**
	 * Creates a new empty graph.
	 */
	public Graph()
	{
		this(new HashMap<Node, Set<Node>>());
	}
	
	private Graph(HashMap<Node, Set<Node>> nodes)
	{
		this.nodes = nodes;
		this.rootGroup = null;
		this.properties = new HashMap<String, Object>();
		this.listeners = new HashSet<GraphEventListener>();
		this.namedNodes = new HashMap<String, Node>();
		this.edgeCount = 0L;
	}
	
	/**
	 * Returns the root group
	 * @return Root group
	 */
	public Group getRootGroup()
	{
	    return rootGroup;
	}
	
	public Group setRootGroup(Group rootGroup)
	{
		Group oldRoot = this.rootGroup;
		this.rootGroup = rootGroup;
		rootGroup.setGraph(this);
		return oldRoot;
	}
	
	public Graph copy()
	{
		Graph g = createNewInstance();
		g.properties = new HashMap<String, Object>(properties);
		
		Map<Node, Node> translation = new HashMap<Node, Node>();
		
		for (Node node : this) {
			Node copiedNode = node.copy();
			g.addNode(copiedNode);
			translation.put(node, copiedNode);
		}
		
		g.setRootGroup(copyGroup(rootGroup, g, translation));
		
		return g;
	}
	
	private Group copyGroup(Group group, Graph newGraph,
		Map<Node, Node> translation)
	{
		Group clone = group.copy();
		
		for (Node node : group) {
			Node newNode = translation.get(node);
			clone.add(newNode);
			
			for (Node neighbor : nodes.get(node)) {
				newGraph.connect(newNode, translation.get(neighbor));
			}
		}
		
		for (Group child : group.getChildGroups()) {
			clone.addChildGroup(copyGroup(child, newGraph, translation));
		}
		
		return clone;
	}
	
	protected Graph createNewInstance()
	{
		return new Graph();
	}
	
	public boolean addEventListener(GraphEventListener listener)
	{
		return this.listeners.add(listener);
	}
	
	public boolean removeEventListener(GraphEventListener listener)
	{
		return this.listeners.remove(listener);
	}
	
	protected HashMap<Node, Set<Node>> copyAdjacencyMap()
	{
		HashMap<Node, Set<Node>> newMap =
			new HashMap<Node, Set<Node>>(nodes.size());
		
		for (Map.Entry<Node, Set<Node>> e : nodes.entrySet()) {
			newMap.put(e.getKey(), new HashSet<Node>(e.getValue()));
		}
		
		return newMap;
	}
	
	public Object getProperty(String name)
	{
		return properties.get(name);
	}
	
	public Object setProperty(String name, Object newValue)
	{
		return properties.put(name, newValue);
	}
	
	public Node getNode(String name)
	{
		return namedNodes.get(name);
	}
	
	public Group commonGroup(Node... nodes)
	{
		Group group = rootGroup;
		
		while (group != null) {
			for (Group child : group.getChildGroups()) {
				if (child.encloses(nodes[0])) {
					for (Node node : nodes) {
						if (!child.encloses(node))
							return group;
					}
					group = child;
					continue;
				}
			}
			
			break;
		}
		
		return group;
	}
	
	/**
	 * Returns a list of the node's neighbors: nodes that are direct successors
	 * of the given node.
	 * @return A list of the node's neighbors, or {@code null} if the node was
	 * not found in the graph
	 * @param node
	 */
	public List<Node> getNeighbors(Node node)
	{
		return new ArrayList<Node>(nodes.get(node));
	}
	
	/**
	 * Returns a list of the nodes of which the given node is a neighbor.
	 * @return A list of the nodes of which the given node is a neighbor
	 * @param node
	 */
	public List<Node> getPredecessors(Node node)
	{
		List<Node> predecessors = new LinkedList<Node>();
		
		for (Map.Entry<Node, Set<Node>> entry : nodes.entrySet()) {
			if (entry.getValue().contains(node))
				predecessors.add(entry.getKey());
		}
		
		return predecessors;
	}
	
	/**
	 * Creates a traverser that walks the graph starting at the given node.
	 */
	BreadthFirstTraverser breadthFirstTraverser(Node node)
	{
		return new BreadthFirstTraverser(this, node);
	}
	
	/**
	 * Finds the shortest path from {@code head} to {@code tail}.
	 * @param head the node to search from
	 * @param tail the node to which the shortest path will be found
	 * @return the shortest path, or {@code null} if {@code tail} is not
	 * reachable from {@code head}
	 */
	public Path findShortestPath(Node head, Node tail)
	{
		for (Path path : breadthFirstTraverser(head)) {
			if (path.getTail().equals(tail))
				return path;
		}
		
		return null;
	}
	
	/**
	 * Finds the shortest path to all nodes starting at {@code head}.
	 * @param head the node to search from
	 */
	public Map<Node, Path> findShortestPaths(Node head)
	{
		return breadthFirstTraverser(head).createMap();
	}
	
	/**
	 * Returns true if the two nodes are directly connected (i.e., by one edge).
	 * @return true if the two nodes are directly connected
	 */
	public boolean connected(Node from, Node to)
	{
		Set<Node> neighbors = nodes.get(from);
		
		return (neighbors != null)
			? neighbors.contains(to)
			: false;
	}
	
	/**
	 * Connects one node on the graph to another.
	 * @param from the head of the new edge
	 * @param to the tail of the new edge
	 * @return true if an edge was created as a result of this call
	 */
	public boolean connect(Node from, Node to)
	{
		Set<Node> neighbors = nodes.get(from);
		
		if (neighbors == null || !nodes.containsKey(to))
			return false;
		
		boolean result = neighbors.add(to);
		if (result) {
			edgeCount++;
			for (GraphEventListener listener : listeners) {
				listener.edgeAdded(this, new Edge(from, to));
			}
		}
		return result;
	}
	
	/**
	 * Disonnects one node on the graph from another.
	 * @param from the head of the doomed edge
	 * @param to the tail of the doomed edge
	 * @return true if an edge was removed as a result of this call
	 */
	public boolean disconnect(Node from, Node to)
	{
		Set<Node> neighbors = nodes.get(from);
		
		if (neighbors == null)
			return false;
		
		boolean result = neighbors.remove(to);
		if (result) {
			edgeCount--;
			for (GraphEventListener listener : listeners) {
				listener.edgeRemoved(this, new Edge(from, to));
			}
		}
		return result;
	}
	
	boolean addNode(Node node)
	{

		if (!nodes.containsKey(node)) {
			nodes.put(node, new HashSet<Node>());
			
			String name = node.getName();
			if (name != null)
				namedNodes.put(name, node);
			
			for (GraphEventListener listener : listeners) {
				listener.nodeAdded(this, node);
			}
			
			return true;
		} else {
			return false;
		}
	}
	
	boolean removeNode(Object node)
	{
		boolean result = nodes.remove(node) != null;
		
		if (result) {
			String name = ((Node) node).getName();
			if (name != null)
				namedNodes.remove(name);
			
			for (GraphEventListener listener : listeners) {
				listener.nodeRemoved(this, (Node) node);
			}
		}
		return result;
	}
	
	public boolean contains(Object node)
	{
		return nodes.containsKey(node);
	}
	
	/**
	 * Returns an iterator of all the nodes in the graph.
	 * @return an iterator
	 */
	public Iterator<Node> iterator()
	{
		return nodes.keySet().iterator();
	}
	
	/**
	 * Returns the number of nodes in the graph.
	 * @return Number of nodes in the graph
	 */
	public int size()
	{
	    return nodes.size();
	}
	
	/**
	 * Returns the number of edges in the graph.
	 * @return Number of edges in the graph.
	 */
	public long edgeCount()
	{
		return this.edgeCount;
	}
	
	/**
	 * Returns the average degree over all nodes in the graph.
	 * @return The average degree over all nodes in the graph
	 */
	public double getAverageDegree()
	{
		double tally = 0.0;
		
		for (Map.Entry<Node,Set<Node>> e : nodes.entrySet()) {
			tally += (double) e.getValue().size();
		}
		
		return (tally / (double) size());
	}
	
	/**
	 * Returns the graph's density.
	 * @return The graph's density
	 */
	public double getDensity()
	{
		long possible = size() * (size() - 1);
		
		return (double) edgeCount / (double) possible;
	}
	
	/**
	 * Returns the set of nodes in the graph
	 * @return Set of nodes in the graph
	 */
	public Set<Node> getNodes()
	{
	    return Collections.unmodifiableSet(nodes.keySet());
	}
	
	/**
	 * Returns the set of edges in the graph
	 * @return Set of edges in the graph
	 */
	public Set<Edge> getEdges()
	{
		Set<Edge> edges = new HashSet<Edge>();
		
		for (Map.Entry<Node, Set<Node>> e : nodes.entrySet()) {
			Node head = e.getKey();
			for (Node tail : e.getValue()) {
				edges.add(new Edge(head, tail));
			}
		}
		
		return edges;
	}
	
	public String toString()
	{
		return String.format("<%s %s>", getClass().getName(),
			getRootGroup());
	}
}
